P3372 【模板】线段树 1

事实上，这篇题解跟线段树没有任何关系。

lifan 让我们用 CDQ 做，但他的标程是假的。

先考虑单点修改+区间求和

数组的初值可以看做 $n$ 个修改操作。

将询问操作拆成 $[1,l)$ 和 $[1,r]$ 两个区间的差。

那么修改 $i$ 对询问 $j$ 有贡献的条件为： $t_i < t_j ,x_i <x_j$

很显然，这是一个二维偏序，具体实现很简单就不讲了。

回到区间修改，一样将修改操作拆成两个区间。

在两个相邻修改区间右端点之间的数修改的值是一样的，所以可以维护这个值。

区间加就可以变为 任意两个相邻修改区间右端点的距离与该部分修改的值的乘积 的和。

不会写归并排序，就用了 STL 里的 merge。

时间复杂度均为 $\mathcal O((n+m) \log (n+m) )$ ，跑不过树状数组/线段树。

所以写这个的意义何在

单点修改+区间查询：

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAXN = 4e6;
int n , m , t , q , Ans[ MAXN + 5 ];
struct node {
	int x , ty , val , id; 
}a[ MAXN + 5 ] , tmp[ MAXN + 5 ];
bool cmp2( const node &x , const node &y ) {
	return x.x < y.x;
}

void CDQ( int l , int r ) {
	if( l == r ) return;
	int Mid = ( l + r ) >> 1;
	CDQ( l , Mid ); CDQ( Mid + 1 , r );
    merge( a + l , a + Mid + 1 , a + Mid + 1 , a + r + 1 , tmp + l , cmp2 ); 
	//sort( a + l , a + Mid + 1 , cmp2 ); sort( a + Mid + 1 , a + r + 1 , cmp2 );
	
	int Sum = 0;
	int i = l , j = Mid + 1; //i->[l,Mid] j->(Mid,r]
	for( ; j <= r ; j ++ ) {
		for( ; i <= Mid && a[ i ].x <= a[ j ].x ; i ++ ) if( a[ i ].ty == 1 ) Sum += a[ i ].val; 
		if( a[ j ].ty == 2 ) Ans[ a[ j ].id ] += a[ j ].val * Sum; 
	}
    for( int i = l ; i <= r ; i ++ ) a[ i ] = tmp[ i ];
}

int main( ) {
	scanf("%d %d",&n,&m);
	for( int i = 1 , x ; i <= n ; i ++ ) {
		scanf("%d",&x);
		a[ ++ t ] = { i , 1 , x };
	}
	for( int i = 1 , opt , l , r , x ; i <= m ; i ++ ) {
		scanf("%d %d %d",&opt,&l,&r);
		if( opt == 1 ) {
			a[ ++ t ] = { l , 1 , r };
		}
		if( opt == 2 ) {
			++ q;
			a[ ++ t ] = { l - 1 , 2 , -1 , q };
			a[ ++ t ] = { r , 2 , 1 , q };
		}
	}
	m = t;
	
	CDQ( 1 , m );
	for( int i = 1 ; i <= q ; i ++ ) printf("%d\n", Ans[ i ] );
	return 0;
}

区间修改+区间查询

#include <cstdio>
#include <algorithm>
using namespace std;
#define LL long long 

const int MAXN = 5e6;
int n , m , t , q;
LL Ans[ MAXN + 5 ];
struct node {
	int x , ty , val , id; 
}a[ MAXN + 5 ] , tmp[ MAXN + 5 ];
bool cmp2( const node &x , const node &y ) {
	return x.x < y.x;
}

void CDQ( int l , int r ) {
	if( l == r ) return;
	int Mid = ( l + r ) >> 1;
	CDQ( l , Mid ); CDQ( Mid + 1 , r );
	merge( a + l , a + Mid + 1 , a + Mid + 1 , a + r + 1 , tmp + l , cmp2 ); 
	
	LL Sum = 0 , val = 0; int last = 0;
	int i = l , j = Mid + 1; //i->[l,Mid] j->(Mid,r]
	for( ; j <= r ; j ++ ) {
		for( ; i <= Mid && a[ i ].x <= a[ j ].x ; i ++ ) {
			Sum += ( a[ i ].x - last ) * val; last = a[ i ].x; 
			if( a[ i ].ty == 1 ) val += a[ i ].val;
		}
		Sum += ( a[ j ].x - last ) * val; last = a[ j ].x;
		if( a[ j ].ty == 2 ) Ans[ a[ j ].id ] += a[ j ].val * Sum; 
	}
	for( int i = l ; i <= r ; i ++ ) a[ i ] = tmp[ i ];
}

int main( ) {
	scanf("%d %d",&n,&m);
	for( int i = 1 , x ; i <= n ; i ++ ) {
		scanf("%d",&x);
		a[ ++ t ] = { i - 1 , 1 , x };
		a[ ++ t ] = { i , 1 , -x };
	}
	for( int i = 1 , opt , l , r , x ; i <= m ; i ++ ) {
		scanf("%d %d %d",&opt,&l,&r);
		if( opt == 1 ) {
			scanf("%d",&x);
			a[ ++ t ] = { l - 1 , 1 , x };
			a[ ++ t ] = { r , 1 , -x };
		}
		if( opt == 2 ) {
			++ q;
			a[ ++ t ] = { l - 1 , 2 , -1 , q };
			a[ ++ t ] = { r , 2 , 1 , q };
		}
	}
	m = t;
	
	CDQ( 1 , m );
	for( int i = 1 ; i <= q ; i ++ ) printf("%lld\n", Ans[ i ] );
	return 0;
}